package com.gitee.feizns.explore.data_structure.string;

/**
 * 43. 字符串相乘
 * @author feizns
 * @since 2020/2/26
 */
public class Multiply {

    public static String multiply234(String num1, String num2) {
        if ( "0".equals(num1) || "0".equals(num2) ) return "0";
        int[] ret = new int[num1.length() + num2.length()];
        for (int i = num2.length() - 1, j = ret.length - 1; i > -1; i--, j--) {
            int k = j;
            int n = toInt(num2.charAt(i));
            int sum = 0;
            for (int l = num1.length() - 1; l > -1; l--) {
                sum += toInt(num1.charAt(l)) * n;
                ret[k] += sum % 10;
                if ( ret[k] > 9 ) {
                    sum += 10;
                    ret[k] = ret[k] % 10;
                }
                sum /= 10;
                k--;
            }
            while (sum != 0) {
                ret[k] += sum % 10;
                if ( ret[k] > 9 ) {
                    sum += 10;
                    ret[k] = ret[k] % 10;
                }
                sum /= 10;
                k--;
            }
        }
        int i = indexOfNotZero(ret);
        StringBuilder r = new StringBuilder();
        for (int j = i; j < ret.length; j++) {
            r.append(ret[j]);
        }
        return r.toString();
    }

    private static int indexOfNotZero(int[] ret) {
        for (int i = 0; i < ret.length; i++) {
            if ( ret[i] != 0 )
                return i;
        }
        return -1;
    }


    public static String multiply(String num1, String num2) {
        char[][] tmp = new char[num2.length()][];
        for (int i = 0; i < num2.length(); i++) {
            String newNum = num1 + zero(i);
            tmp[i] = multiply(newNum, num2.charAt(num2.length() - 1 - i));
        }
        return plus(tmp);
    }

    private static String zero(int x) {
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < x; i++)
            ret.append("0");
        return ret.toString();
    }

    public static char[] multiply(String n, char x) {
        StringBuilder ret = new StringBuilder();
        int dx = toInt(x);
        int sum = 0;
        for (int i = n.length() - 1; i >= 0; i--) {
            sum += toInt(n.charAt(i)) * dx;
            ret.insert(0, toChar(sum % 10));
            sum = sum / 10;
        }
        if ( sum != 0 )
            ret.insert(0, toChar(sum % 10));
        return ret.toString().toCharArray();
    }

    public static String plus(char[]... chars) {
        int len = maxLen(chars);
        StringBuilder ret = new StringBuilder();
        int sum = 0;
        for (int i = 0; i < len; i++) {
            for (char[] c : chars) {
                int offset = c.length - 1 - i;
                if ( offset > -1 )
                    sum += toInt(c[offset]);
            }
            ret.insert(0, toChar(sum % 10));
            sum = sum / 10;
        }
        if ( sum != 0 )
            ret.insert(0, toChar(sum % 10));
        return trimZero(new String(ret));
    }

    private static int toInt(char a) {
        return (int) a - (int) '0';
    }

    private static char toChar(int x) {
        return Character.forDigit(x, 10);
    }

    private static int maxLen(char[][] chars) {
        int ret = 0;
        for (char[] c : chars) {
            if ( c.length > ret )
                ret = c.length;
        }
        return ret;
    }

    private static String trimZero(String n) {
        String tmp = n.trim();
        StringBuilder ret = new StringBuilder();
        int i = 0;
        while ( i < tmp.length() ) {
            if ( tmp.charAt(i) != '0' )
                break;
            i++;
        }
        return i == tmp.length() ? "0" : ret.append(tmp, i, tmp.length()).toString();
    }

    public static void main(String[] args) {
//        System.out.println(toChar(2));
//        System.out.println(Integer.valueOf('2'));
        System.out.println(multiply234("123", "456"));
//        System.out.println(plus(new char[]{'1', '2', '0'}, new char[]{'1', '1', '1'}));
    }

}
